12.8 KB · ⇊ 5 parts · ⤓ Micron 12.8 KB · ⤓ HTML 57.4 KB

top

Il mwbqDBSCAN (mwbgDensity-Based Spatial Clustering of Applications with Noise) è un metodo di mwbwclustering proposto nel mwca1996 da Martin Ester, Hans-Peter Kriegel, Jörg Sander e Xiaowei Xu. È basato sulla densità perché connette regioni di punti con densità sufficientemente alta. DBSCAN è l'algoritmo più comunemente usato ed è anche il più citato nella letteratura scientifica.

• Idea fondamentale

• Algoritmo

• Pseudo codice

• Complessità

• Vantaggi

• Svantaggi

• Rilevamento vicinato più vicino

• Stima dei parametri

• Altro

DBSCAN usa una definizione di cluster basata sulla nozione di mwfqdensità.

Un punto mwfw q {\displaystyle q} è mwgadirettamente raggiungibile da un altro punto mwgq p {\displaystyle p} se la distanza fra essi è minore di un mwgg ε ε {\displaystyle \varepsilon } fissato (cioè, se mwgw q {\displaystyle q} è parte del cosiddetto mwha ε ε {\displaystyle \varepsilon } -vicinato di mwhq p {\displaystyle p} ; ovviamente tale relazione è mwhgsimmetrica). Se nell'mwhw ε ε {\displaystyle \varepsilon } -vicinato di mwia p {\displaystyle p} è presente un numero minimo mwiq M {\displaystyle M} di punti, mwig p {\displaystyle p} è detto un mwiwnucleo (mwjacore point). Più precisamente, nel formalismo di DBSCAN si parla di raggiungibilità diretta solo da un nucleo ad altri punti, e non viceversa, e dunque a rigore la raggiungibilità diretta non è più una relazione simmetrica.

Un punto mwjg r {\displaystyle r} è raggiungibile mwjwper densità da un nucleo mwka p {\displaystyle p} se esiste una sequenza di punti mwkq p 1 , … … , p n {\displaystyle p_{1},\ldots ,p_{n}} di punti con mwkg p 1 = p {\displaystyle p_{1}=p} e mwkw p n = r {\displaystyle p_{n}=r} in cui ogni mwla p i + 1 {\displaystyle p_{i+1}} è direttamente raggiungibile da mwlq p i {\displaystyle p_{i}} . Ciò implica che tutti i punti intermedi siano nuclei, mentre mwlg r {\displaystyle r} potrebbe non esserlo (cioè potrebbe non avere almeno mwlw M {\displaystyle M} punti nel suo mwma ε ε {\displaystyle \varepsilon } -vicinato): la relazione di raggiungibilità per densità non è perciò generalmente simmetrica. I punti non raggiungibili da alcun altro punto sono detti "esterni" (mwmqoutlier).

Si considera dunque come cluster di mwmw p {\displaystyle p} lo stesso mwna p {\displaystyle p} e tutti i punti che sono raggiungibili (per densità) da esso. Ogni cluster contiene almeno un punto nucleo, e quelli che non lo sono vengono detti "margini" (mwnqedge): sono punti da cui non possono esserne raggiunti altri. Far parte dello stesso cluster è una relazione simmetrica che può essere formalizzata (in modo abbastanza ridondante, ma necessario per la definizione "orientata" di raggiungibilità diretta in DBSCAN) tramite la nozione di mwngconnessione per densità (mwnwdensity-connectedness): due punti mwoa p {\displaystyle p} e mwoq q {\displaystyle q} sono mwogconnessi per densità se esiste un punto mwow o {\displaystyle o} tale che sia mwpa p {\displaystyle p} che mwpq q {\displaystyle q} siano raggiungibili (per densità) da mwpg o {\displaystyle o} .

Un cluster, che è un sotto-insieme dei punti dell'insieme di dati, soddisfa due proprietà:

1. Tutti i punti all'interno del cluster sono mutuamente connessi per densità.

2. Se un punto è raggiungibile per densità da un altro punto del cluster, anch'esso è parte del cluster.

DBSCAN necessita di due parametri: mwrq ε ε {\displaystyle \varepsilon } (eps) e del numero minimo di punti richiesti per formare un cluster (minPts). Si comincia con un punto casuale che non è stato ancora visitato. Viene calcolato il suo mwrg ε ε {\displaystyle \varepsilon } -vicinato e se contiene un numero sufficiente di punti viene creato un nuovo cluster. Se ciò non avviene il punto viene etichettato come rumore e successivamente potrebbe essere ritrovato in un mwrw ε ε {\displaystyle \varepsilon } -vicinato sufficientemente grande riconducibile ad un punto differente entrando a far parte di un cluster.

Se un punto è associato ad un cluster anche i punti del suo mwsq ε ε {\displaystyle \varepsilon } -vicinato sono parte del cluster. Conseguentemente tutti i punti trovati all'interno del suo mwsg ε ε {\displaystyle \varepsilon } -vicinato sono aggiunti al cluster, così come i loro mwsw ε ε {\displaystyle \varepsilon } -vicinati. Questo processo continua fino a quando il cluster viene completato. Il processo continua fino a quando non sono stati visitati tutti i punti.

DBSCAN visita ogni punto del database, anche più volte nel caso di punti candidati a cluster differenti. Tuttavia per considerazioni pratiche la complessità temporale è per lo più governata dal numero di invocazioni a getVicini, in riferimento allo pseudo codice di cui sopra. DBSCAN esegue esattamente una invocazione per ogni punto e se viene utilizzata una struttura indicizzata che esegue un'interrogazione del vicinato in mwug O ( log ⁡ ⁡ n ) {\displaystyle O(\log n)} , si ottiene un tempo globale di esecuzione pari a mwuw O ( n ⋅ ⋅ log ⁡ ⁡ n ) {\displaystyle O(n\cdot \log n)} . Senza l'uso di strutture indicizzate, il tempo di esecuzione è pari a mwva O ( n 2 ) {\displaystyle O(n^{2})} . Spesso la matrice delle distanze di dimensione mwvq ( n 2 − − n ) / 2 {\displaystyle (n^{2}-n)/2} viene creata per evitare appunto il ricalcolo delle distanze riducendo il tempo di elaborazione a spese della memoria utilizzata pari a mwvg O ( n 2 ) {\displaystyle O(n^{2})} .

DBSCAN presenta i seguenti vantaggi:

• non richiede di conoscere il numero di cluster a priori, al contrario dell'mwwwalgoritmo K-means;

• può trovare cluster di forme arbitrarie. Può anche trovare un cluster completamente circondato da un cluster differente a cui non è connesso (dato il parametro MinPts, il cosiddetto effetto single-link, cluster differenti connessi da una sottile linea di punti, viene ridotto);

• possiede la nozione di rumore;

• richiede soltanto due parametri ed è per lo più insensibile all'ordine dei punti nel database: solo i punti posti sull'arco fra due cluster differenti possono cambiare la loro appartenenza se l'ordine dei punti viene cambiato mentre l'assegnazione ai cluster è unico a meno di isomorfismi.

1. La qualità del clustering generato da DBSCAN dipende dalla sua mwygmisura della distanza che è riconducibile alla funzione getVicini(P, epsilon). La più comune misura usata è la mwywdistanza euclidea. In particolare per il high-dimensional data, questa misura della distanza diventa quasi inutile tanto da esser denominata "Maledizione della dimensionalità"; nei fatti diventa difficile trovare un valore appropriato per epsilon. Tuttavia questo effetto è presente anche in altri algoritmi basati sulla distanza euclidea.

2. DBSCAN non è in grado di classificare insiemi di dati con grandi differenze nelle densità, dato che la combinazione minPts-epsilon non può poi essere scelta in modo appropriato per tutti i cluster.

Guarda la sezione in basso sulle estensioni per modifiche algoritmiche che gestiscono queste caratteristiche.

Il rilevamento del vicinato più vicino avviene nella funzione getVicini(P,epsilon). Per ogni punto P vengono determinati tutti gli altri punti che sono all'interno dell'intervallo epsilon, basandosi sulla funzione della distanza usata nell'algoritmo. L'analisi richiede che sia calcolata una matrice delle distanze per l'intero data set. La generazione della matrice delle distanze ha una complessità di mwbq O ( ( n 2 − − n ) / 2 ) {\displaystyle O((n^{2}-n)/2)} dato che è necessaria solo una mwbgmatrice triangolare superiore. All'interno della matrice delle distanze il vicinato più vicino può essere calcolato selezionando la tupla che ha come valori il minimo delle funzioni su riga e colonna. La ricerca ha spinto il rilevamento del vicinato, nei database tradizionali, per migliorare la velocità. Questi ultimi risolvono il problema utilizzando mwbwindici specificamente progettati per questo tipo di applicazioni.

Ogni processo di mwcgdata mining ha il problema dei parametri. Ogni parametro influenza l'algoritmo in modo specifico. Per il DBSCAN i parametri epsilon e MinPnts sono necessari. I parametri devono essere specificati dall'utente dato che ogni data set richiede parametri differenti. Un valore iniziale per mwcw ε ε {\displaystyle \varepsilon } può essere determinato come un k-distance graph. Come regola generale, mwdq k {\displaystyle k} può essere derivato dal numero di dimensioni nel data set mwdg D {\displaystyle D} come mwdw k = | D | + 1 {\displaystyle k=|D|+1} . Tuttavia valori maggiori sono generalmente migliori per data set con rumore.

Anche se questa stima dei parametri restituisce un insieme sufficiente di parametri, la classificazione risultante può rivelarsi diversa da ciò che si aspetta, pertanto la ricerca ha realizzato un'ottimizzazione incrementale dei parametri su particolari valori.

Per ogni oggetto vengono trovati i vicini che ricadono in un raggio dato come parametro in ingresso; se il numero di questi vicini è superiore ad un fattore di soglia, anch'esso fornito in input all'mwewalgoritmo, allora questi punti fanno parte del medesimo cluster di quello dell'oggetto che si sta osservando e in questo caso il punto è denominato mwfacore point.

Al termine dell'algoritmo ci potrebbero essere alcuni punti non appartenenti a cluster catalogati come mwfgrumore.

Se c'è una catena di oggetti da attraversare (con i consueti vincoli) per raggiungere un punto mwgaq da uno mwgqp, allora mwggq sarà detto semplicemente mwgwrintracciabile.

Ultimo caso è quello in cui due oggetti "p" e "q" sono detti mwhqconnessi: per essere definiti in tal modo, deve esistere un terzo punto mwhgo, per cui "p" e "q" sono entrambi rintracciabili.